public class ListNode {
       int val;
       ListNode next;
       ListNode() {}
       ListNode(int val) { this.val = val; }
       ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 }

class Solution {
    /**
     * 给你单链表的头节点 head,如何反转链表并返回反转后的链表?
     * 解法 1:迭代解法
     * @param head 给定链表的头节点
     * @return 反转链表后的头节点
     */
    public ListNode reverseList(ListNode head) {
        //如果链表为空或链表仅有一个元素则无需进行反转
        if (head == null || head.next == null) return head;
        //记录当前节点
        ListNode cur = head.next;
        //初始的头节点反转后将成为最后一个节点,故将 next域置为 null
        head.next = null;
        //遍历当前链表
        while(cur != null) {
            //记录当前节点的后驱节点
            ListNode next = cur.next;
            //反转链表
            cur.next = head;
            //移动头节点
            head = cur;
            //移动当前节点
            cur = next;
        }
        //此时 head为反转链表后新链表的头节点
        return head;
    }

    /**
     * 给你单链表的头节点 head,如何反转链表并返回反转后的链表?
     * 解法 2:递归解法
     * @param head 给定链表的头节点
     * @return 反转链表后的头节点
     */
    public ListNode reverseList2(ListNode head) {
        //如果链表为空或链表仅有一个元素则无需进行反转,递归跳出条件
        if (head == null || head.next == null) return head;
        //不断反转最小子表
        ListNode node = reverseList(head.next);
        //反转链表
        head.next.next = head;
        head.next = null;
        //返回反转链表后的新头节点
        return node;


    }
}